package cn.edu.jxau.test;

import cn.edu.jxau.util.LinkedQueue;
import cn.edu.jxau.util.LinkedStack;
import cn.edu.jxau.util.Queue;
import cn.edu.jxau.util.Stack;

public class DirectedPaths {

    public static void main(String[] args) {

        DirectedGraph g = new DirectedGraph(13);
        g.addEdge(4, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 2);
        g.addEdge(6, 0);
        g.addEdge(0, 1);
        g.addEdge(2, 0);
        g.addEdge(11, 12);
        g.addEdge(12, 9);
        g.addEdge(9, 10);
        g.addEdge(9, 11);
        g.addEdge(8, 9);
        g.addEdge(10, 12);
        g.addEdge(11, 4);
        g.addEdge(4, 3);
        g.addEdge(3, 5);
        g.addEdge(7, 8);
        g.addEdge(8, 7);
        g.addEdge(5, 4);
        g.addEdge(0, 5);
        g.addEdge(6, 4);
        g.addEdge(6, 9);
        g.addEdge(7, 6);

        DirectedPaths dp = new DirectedPaths(g, 0);
        for (int i = 0; i < g.v(); i++) {
            if(dp.hasPathTo(i)) {
                for(int j : dp.pathTo(i)) {
                    System.out.print(j+" ");
                }
            }
            System.out.println();
        }
    }

    /**
     * 标记
     */
    private boolean[] marked;

    /**
     * 路径信息
     */
    private int[] edgeTo;

    /**
     * 起点
     */
    private int start;

    public DirectedPaths(DirectedGraph g, int start) {

        marked = new boolean[g.v()];
        edgeTo = new int[g.v()];
//        dfs(g, start);
        bfs(g,start);
    }

    /**
     * 深度优先遍历：单点有向路径
     * @param g
     * @param v
     */
    private void dfs(DirectedGraph g, int v) {

        marked[v] = true;
        for (int w : g.adj(v)) {
            if (!marked[w]) {
                edgeTo[w] = v;// 建立路径信息
                dfs(g, w);
            }
        }
    }

    /**
     * 广度优先遍历：单点最短有向路径
     * @param g
     * @param v
     */
    private void bfs(DirectedGraph g, int v) {

        marked[v] = true;
        Queue<Integer> queue = new LinkedQueue<Integer>();
        queue.enqueue(start);
        while (!queue.isEmpty()) {
            int w = queue.dequeue();
            for (int i : g.adj(w)) {
                if (!marked[i]) {
                    marked[i] = true;
                    edgeTo[i] = w; // 建立路径信息
                    queue.enqueue(i);
                }
            }
        }
    }

    /**
     * 从起点start到v是否存在一条路径
     * @param v
     * @return
     */
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    /**
     * 从起点start到v的路径信息
     * @param v
     * @return
     */
    public Iterable<Integer> pathTo(int v) {

        Stack<Integer> stack = new LinkedStack<>();
        while (v != start) {
            stack.push(v);
            v = edgeTo[v];
        }
        stack.push(start);
        return stack;
    }
}